A common feature of these applications is that there are multiple decision makers interacting with each other in a common environment.

As the set of solutions to Eq. (3.4) is a line parallel to the subspace A.2 Proof of Lemma 2 For every θ E, we have Φ θ null= e . The auxiliary algorithm (A.1) can be rewritten in the following vector form Θ Bellman operator H is indifferent, i.e., H ( Q + x) H (Q) E, x E So it is impossible to apply the finite time analysis in the literature to establish the convergence of the iterates to some fix point. Then the following properties hold. Lemma 4.a) implies that (c So the Lemma 4.b) implies c Proposition 2. If M is L-smooth with respect to null null Now let's analyze the iterates generated by the following stochastic approximation scheme for solving We make the following assumptions regarding the function H and its stochastic sample ˆ H . Assumption 4. 1. H A and B . 3. There exist a fixed equivalent class, i.e., x Now we study the last term. Now let's focus on the last term in Notice that the monotonicity of infimal convolution (Lemma 4.a) and Lemma 4.b)) implies By update rule (B.5), we have E[ null null x Let's consider the decreasing stepsize first.

How much data is required to guarantee a given level of accuracy?

Despite their spectacular progress, language models still struggle on complex reasoning tasks, such as advanced mathematics.We consider a long-standing open problem in mathematics: discovering a Lyapunov function that ensures the global stability of a dynamical system. This problem has no known general solution, and algorithmic solvers only exist for some small polynomial systems.We propose a new method for generating synthetic training samples from random solutions, and show that sequence-to-sequence transformers trained on such datasets perform better than algorithmic solvers and humans on polynomial systems, and can discover new Lyapunov functions for non-polynomial systems.

We propose new methods for learning control policies and neural network Lyapunov functions for nonlinear control problems, with provable guarantee of stability. The framework consists of a learner that attempts to find the control and Lyapunov functions, and a falsifier that finds counterexamples to quickly guide the learner towards solutions. The procedure terminates when no counterexample is found by the falsifier, in which case the controlled nonlinear system is provably stable. The approach significantly simplifies the process of Lyapunov control design, provides end-to-end correctness guarantee, and can obtain much larger regions of attraction than existing methods such as LQR and SOS/SDP. We show experiments on how the new methods obtain high-quality solutions for challenging robot control problems such as path tracking for wheeled vehicles and humanoid robot balancing.

Learning for control of dynamical systems with formal guarantees remains a challenging task. This paper proposes a learning framework to simultaneously stabilize an unknown nonlinear system with a neural controller and learn a neural Lyapunov function to certify a region of attraction (ROA) for the closed-loop system with provable guarantees. The algorithmic structure consists of two neural networks and a satisfiability modulo theories (SMT) solver. The first neural network is responsible for learning the unknown dynamics. The second neural network aims to identify a valid Lyapunov function and a provably stabilizing nonlinear controller. The SMT solver verifies the candidate Lyapunov function satisfies the Lyapunov conditions. We further provide theoretical guarantees of the proposed learning framework and show that the obtained Lyapunov function indeed verifies for the unknown nonlinear system under mild assumptions. We illustrate the effectiveness of the results with a few numerical experiments.

Deep networks are commonly used to model dynamical systems, predicting how the state of a system will evolve over time (either autonomously or in response to control inputs). Despite the predictive power of these systems, it has been difficult to make formal claims about the basic properties of the learned systems. In this paper, we propose an approach for learning dynamical systems that are guaranteed to be stable over the entire state space. The approach works by jointly learning a dynamics model and Lyapunov function that guarantees non-expansiveness of the dynamics under the learned Lyapunov function. We show that such learning systems are able to model simple dynamical systems and can be combined with additional deep generative models to learn complex dynamics, such as video textures, in a fully end-to-end fashion.